#include <algorithm>
#include <cstdio>
constexpr int MaxL = 1e7 + 5;
int q;
int vis[MaxL];
inline long long gcd(long long x, long long y)
{
    for (;;)
    {
        if (x == y || y == 0)
        {
            return x;
        }
        else if (x == 0)
        {
            return y;
        }
        else if (x > y)
        {
            x %= y;
        }
        else
        {
            y %= x;
        }
    }
}
inline long long lcm(long long x, long long y)
{
    return x * y / gcd(x, y);
}
inline void init(int limit = 1e7)
{
    for (int i = 2; i <= limit; i++)
    {
        for (int j = i * 2; j <= limit; j += i)
        {
            if (vis[j] == 0)
            {
                vis[j] = i;
            }
        }
    }
}
long long solve(long long x, long long y)
{
    if (x == 0 || y == 0)
    {
        return 1e15;
    }
    long long g = gcd(x, y);
    if (g == 1)
    {
        if (vis[x] == 0 && vis[y] == 0)
        {
            return std::min(x * y, 2 * x + 2 * y);
        }
        return std::min({x * y, 2 * x + 2 * y, x + solve(vis[x], y), solve(x, vis[y]) + y});
    }
    else if (g == x)
    {
        return y;
    }
    else
    {
        return x + y;
    }
}
int main()
{
    freopen("never.in", "r", stdin);
    freopen("never.out", "w", stdout);
    init();
    scanf("%d", &q);
    for (int i = 1; i <= q; i++)
    {
        long long x, y;
        scanf("%lld%lld", &x, &y);
        printf("%lld\n", solve(x, y));
    }
    return 0;
}